package ViolenceRecursive;

/**
 * @author Liaorun
 */
public class BurstBalloons {

    public static void main(String[] args) {
        System.out.println(maxCoins1(new int[]{3, 2, 5}));
    }


    public static int maxCoins1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        if (arr.length == 1) {
            return arr[0];
        }

        int N = arr.length;
        int[] help = new int[N + 2];

        // 给原数组开始和结尾添加一个1，方便后期的编辑处理，不会影响结果
        // example: arr: 345 -> help： 13451
        help[0] = 1;
        help[N + 1] = 1;
        for (int i = 0; i < N; i++) {
            help[i + 1] = arr[i];
        }

        return process(help, 1, N);
    }

    /**
     * 打爆arr[l..r]范围上的所有的气球，返回最大的分数
     * 假设arr[l-1]和arr[r+1]一定没有被打爆
     *
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int process(int[] arr, int l, int r) {
        // 如果只有一个气球了，直接打爆
        if (l == r) {
            return arr[l - 1] * arr[l] * arr[r + 1];
        }

        // 最后打爆arr[l]的方案，和最后打爆arr[r]的方案，先比较一下
        int max = Math.max(arr[l - 1] * arr[l] * arr[r + 1] + process(arr, l + 1, r), arr[l - 1] * arr[r] * arr[r + 1] + process(arr, l, r - 1));

        // 尝试中间位置的气球最后被打爆的每一种方案
        for (int i = l + 1; i < r; i++) {
            max = Math.max(max, arr[l - 1] * arr[i] * arr[r + 1] + process(arr, l, i - 1) + process(arr, i + 1, r));
        }

        return max;
    }


    public static int maxCoins2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        if (arr.length == 1) {
            return arr[0];
        }

        int N = arr.length;
        int[] help = new int[N + 2];

        // 给原数组开始和结尾添加一个1，方便后期的编辑处理，不会影响结果
        // example: arr: 345 -> help： 13451


        return 0;
    }
}
